package com.lihepeng.leecode.classic;

import java.util.Stack;

import org.junit.Test;

/**
 * 链表反转
 *
 * @author lihepeng
 */
public class RevertLink {
    /**
     * 反转链表 fuc1
     * 借助堆栈结构完成业务
     *
     * @param node
     * @return
     */
    public Node revertfuc(Node node) {
        Stack<Node> stack = new Stack<>();
        while (node != null) {
            stack.push(node);
            node = node.getNext();
        }
        Node currentNode = null;
        Node lastNode = null;
        while (!stack.isEmpty()) {
            Node node2 = stack.pop();
            if (currentNode == null) {
                currentNode = node2;
                lastNode = currentNode;
            } else {
                node2.setNext(null);
                currentNode.setNext(node2);
                currentNode = node2;
            }
        }

        return lastNode;
    }

    /**
     * 链表的头部插入
     */
    public Node headerInsert(Node newNode, Node currentNode) {
        newNode.setNext(currentNode);
        return newNode;
    }

    /**
     * 反转链表方法2
     * 遍历反转
     *
     * @return
     */
    public Node revertFuc2(Node headNode) {
        if (headNode == null) {
            return headNode;
        }
        Node pre = headNode;
        Node currentNode = headNode.getNext();
        Node tem = null;
        while (currentNode != null) {
            tem = currentNode.getNext();
            currentNode.setNext(pre);
            pre = currentNode;
            currentNode = tem;
        }
        headNode.setNext(null);
        return pre;

    }

    @Test
    public void runFunc() {
        Node node = new Node("1");
        Node node1 = new Node("2");
        Node node2 = new Node("3");
        Node node3 = new Node("4");
        Node node4 = new Node("5");
        node.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        Node nodex = this.revertFuc2(node);
        printNode(nodex);

    }

    public void printNode(Node node) {
        StringBuffer sb = new StringBuffer();
        while (node != null) {
            sb.append(node.getValue());
            sb.append("->");
            node = node.getNext();
        }
        System.out.println(sb.toString());
    }

    // 头部插入测试
    @Test
    public void runTest03() {
        Node head = new Node("1");
        Node headerInsert = this.headerInsert(new Node("2"), head);
        this.printNode(headerInsert);

    }
}


class Node {
    private String value;
    private Node next;

    public Node(String value) {
        super();
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }


}
